package com.evolved.automata;
import java.util.regex.*;
import java.util.*;


public class AITools {
	public static int PointToIndex(int Width, int Height, int i, int j)
	{
		return Width*j+i;
	}
	
	public static int[] IndexToPoint(int Width, int Height, int index)
	{
		return new int[] {index%Width,(int)Math.floor(index/Width) };
	}
	
	// Rounds a value to the nearest increment of stepSize
	
	public static double StepFunction(double baseValue, double stepSize)
	{
		int div = (int) Math.round(baseValue/stepSize);
		return div*stepSize;
	}
	
	public static <T> T FirstNonNull(T... params)
	{
		for (T arg: params)
		{
			if (arg!=null)
				return arg;
				
		}
		return null;
	}
	
	public static int PointToIndex(int Width, int Height, IntPair position)
	{
		return Width*position.GetSecond()+position.GetFirst();
	}
	
	public static IntPair IndexToPair(int Width, int Height, int index)
	{
		return new IntPair(index%Width,(int)Math.floor(index/Width));
	}
	
	public static IntPair[] ParsePointList(String pointList)
	{
		String numberPatternString = "\\d\\d*";
		String pointPatternString = String.format("\\(\\s*%1$s\\s*,\\s*%1$s\\s*\\)", numberPatternString);
		
		Pattern pairPattern=Pattern.compile(pointPatternString);
		
		Matcher matcher = pairPattern.matcher(pointList);
		LinkedList<IntPair> listPair = new LinkedList<IntPair>();
		IntPair nextpair=null;
		while (matcher.find())
		{
			nextpair=ParseIntPairString(matcher.group());
			listPair.add(nextpair);
		}
		return (IntPair[])listPair.toArray(new IntPair[0]);
	}
	
	public static IntPair ParseIntPairString(String pairString)
	{
		String strippedLeftPar=pairString.replace("(","");
		String strippedRightPar=strippedLeftPar.replace(")", "");
		String strippedSpaces=strippedRightPar.replace(" ", "");
		String[] numParts = strippedSpaces.split(",");
		return new IntPair(Integer.parseInt(numParts[0]),Integer.parseInt(numParts[1]));
		
	}
	
	public static String SimplifyString(String inputString)
	{
		//return inputString.toLowerCase().replace(" ", "").replace("-", "").replace("_", "");
		return inputString.toLowerCase();
	}
	
	public static IntPair GetRandomIntPair(int minX, int minY, int maxX, int maxY)
	{
		int first = (int)(minX+ Math.random()*(maxX-minX));
		int second = (int)(minY+ Math.random()*(maxY-minY));
		return new IntPair(first, second);
	}
	
	public static int[] GetSurroundingIndices(int i, int j, int minWidth, int minHeight, int maxWidth, int maxHeight, int Width, int Height)
	{
		int left=PointToIndex(Width, Height, i-1,j);
		int tleft = PointToIndex(Width, Height, i-1,j-1);
		int top =PointToIndex(Width, Height, i,j-1);
		int tright = PointToIndex(Width, Height, i+1,j-1);;
		int right=PointToIndex(Width, Height, i+1,j);
		int bright =PointToIndex(Width, Height, i+1,j+1);
		int bottom = PointToIndex(Width, Height, i,j+1);
		int bleft = PointToIndex(Width, Height, i-1,j+1);;
		
		// top left corner
		if ((i==minWidth)&&(j==minHeight))
			return new int[]{right,bright,bottom};
		
		// top middle
		
		if ((minWidth<i)&&(i<maxWidth)&&(j==minHeight))
			return new int[]{left,right,bright,bottom,bleft};
		// top right corner
		if ((i==maxWidth)&&(j==minHeight))
			return new int[]{left,bottom,bleft};
		// right
		if ((minHeight<j)&&(j<maxHeight)&&(i==maxWidth))
			return new int[]{left,tleft,top,bottom,bleft };
		// bottom right corner
		if ((j==maxHeight)&&(i==maxWidth))
			return new int[]{left,tleft,top };
		// bottom 
		if ((j==maxHeight)&&(minWidth<i)&&(i<maxWidth))
			return new int[]{left,tleft,top,tright,right };
		
		// bottom left corner
		if ((j==maxHeight)&&(i==minWidth))
			return new int[]{top,tright,right };
		
		// left
		if ((minHeight<j)&&(j<maxHeight)&&(i==minWidth))
			return new int[]{top,tright,right,bright,bottom };
		else // middle
			return new int[]{left,tleft, top,tright,right,bright,bottom,bleft };
		
	}
	
	/**
	 * Uniformly selects a random element of generic type V from a list of values
	 * 
	 * @param itemList
	 */
	public static <V> V ChooseRandom(List<V> itemList)
	{
		if ((itemList==null)||(itemList.size()<1))
			return null;
		else
		{
			int maxIndex=itemList.size();
			int chosenIndex=(int)Math.min(Math.random()*maxIndex, maxIndex-1);
			return itemList.get(chosenIndex);
		}
	}
	
	/**
	 * Uniformly selects a random element of generic type V from an array of values.
	 * 
	 * @param itemArray
	 */
	public static <V> V ChooseRandom(V[] itemArray)
	{
		if ((itemArray==null)||(itemArray.length<1))
			return null;
		else
		{
			int maxIndex=itemArray.length;
			int chosenIndex=(int)Math.min(Math.random()*maxIndex, maxIndex-1);
			return itemArray[chosenIndex];
		}
	}
	/**
	 * This function implements a slightly altered version of simulated sampling from
	 * a Bernoulli urn filled with colored balls.  With this function, colors with
	 * more balls are weighted slightly more than it would from a completely fair
	 * uniform sampling.  This function only works properly  when the weights are non-
	 * negative. TODO: Fix this so that the maximum and minimum weights are arbitrary
	 * and introduction an error and comparison scale as is done with
	 * ChooseWeightedRandomPartition
	 * 
	 * @param itemList
	 * @param favor_high    favor_high
	 */
	public static <V> WeightedValue<V> ChooseWeightedRandom(List<WeightedValue<V>> itemList, boolean favor_high)
	{
		if ((itemList==null)||(itemList.size()<1))
			return null;
		else
		{
			
			double maxValue=0;
			double weightFactor=(favor_high)?1:-1;
			int randomPrec=10000;
			int cutoff;
			for (WeightedValue<V> wValue: itemList)
			{
				if (wValue.GetWeight()>=maxValue)
					maxValue=wValue.GetWeight();
			}
			cutoff =  (int)(maxValue*Math.random()*randomPrec);
			List<WeightedValue<V>> choiceList = new LinkedList<WeightedValue<V>>();
			for (WeightedValue<V> potential:itemList)
			{
				if (weightFactor*potential.GetWeight()*randomPrec>=weightFactor*cutoff)
					choiceList.add(potential);
			}
			return ChooseRandom(choiceList);
		}
	}
	
	/**
	 * This function simulates sampling from a Bernoulli urn filled with colored balls.
	 * Each element of 'itemList' represents a 'color' and the number of balls is
	 * modeled as a double precision float.  The actual thing that is selected is the
	 * generic parameter V.  This only works with non-negative double precision
	 * weights. TODO: Introduction an error and comparison scale as is done with
	 * ChooseWeightedRandomPartition
	 * 
	 * @param itemList    itemList
	 */
	public static <V> WeightedValue<V> ChooseWeightedRandomFair(List<WeightedValue<V>> itemList)
	{
		if ((itemList==null)||(itemList.size()<1))
			return null;
		else
		{
			
			double cutoff;
			double totalWeight=0;
			for (WeightedValue<V> wValue: itemList)
			{
				totalWeight+=wValue.GetWeight();
			}
			cutoff =  totalWeight*Math.random();
			double pastRange=0,weight;
			
			WeightedValue<V> chosen=null;
			
			
			for (WeightedValue<V> wValue:itemList)
			{
				
				weight=wValue.GetWeight();
				
				if ((weight+pastRange)>=cutoff)
				{
					chosen= wValue;
					break;
				}
				pastRange+=weight;
			}
			return chosen;
			
		}
	}
	
	public static <V> WeightedValue<V> ChooseWeightedRandomLowest(List<WeightedValue<V>> itemList)
	{
		double minValue=0, maxValue=0;
		boolean first=true;
		double error=0;
		
		for (WeightedValue<V> item:itemList)
		{
			if (first)
			{
				minValue=item.GetWeight();
				maxValue=item.GetWeight();
				first=false;
			}
			else
			{
				if (item.GetWeight()- maxValue>= -error/2)
					maxValue=item.GetWeight();
				if (minValue - item.GetWeight()>=-error/2)
					minValue=item.GetWeight();
			}
			
			
		}
		double selectionWidth=maxValue-minValue;
		
		if (Math.abs(selectionWidth)<=error)
			return ChooseRandom(itemList);
		
		int randomScale=1000; // 
		
		double cutoff=Math.floor(randomScale*Math.random());
		
		double cutoffFraction=cutoff/randomScale;
		
		LinkedList<WeightedValue<V>> selectionList = new LinkedList<WeightedValue<V>>();
		
		double offsetFromMin=0;
		double selectionFraction;
		for (WeightedValue<V> item:itemList)
		{
			offsetFromMin=item.GetWeight()-minValue;
			selectionFraction=offsetFromMin/selectionWidth;
			if (selectionFraction < cutoffFraction)
				selectionList.add(item);
		}
		
		return ChooseRandom(selectionList);
	}
	
	
	/**
	 * This method selects a sublist from the List of WeightedValues, {itemList},
	 * where the probability of a WeightedValue being in that list is proportional to
	 * whether that element is closer to the largest weighted value in that list or
	 * the lowest weighted value, depending on the value of {favor_high}.  All double
	 * precision comparisons are to 3 significant digits.  This method calls the base
	 * {ChooseWeightedRandomPartition} method with an error of 1/1000 and a random
	 * scale of 1000.
	 * 
	 * @param itemList
	 * @param favor_high
	 */
	public static <V> LinkedList<WeightedValue<V>> ChooseWeightedRandomPartition(LinkedList<WeightedValue<V>> itemList, boolean favor_high)
	{
		return ChooseWeightedRandomPartition(itemList, favor_high,1.0/1000.0,1000);
	}
	
	
	/**
	 * This method selects a sublist from the List of WeightedValues, {itemList},
	 * where the probability of a WeightedValue being in that list is proportional to
	 * whether that element is closer to the largest weighted value in that list or
	 * the lowest weighted value, depending on the value of {favor_high}.  {error}
	 * should be a small positive value that is used to determine how close two double
	 * value weights can be before they are considered equal.  {randomScale} is used
	 * generally to define the number of significant digits for all double precision
	 * comparisons and should be a power of 10.  The value of {error} should be less
	 * than 1/{randomScale}
	 * 
	 * @param itemList
	 * @param favor_high
	 * @param error
	 * @param randomScale
	 */
	public static <V> LinkedList<WeightedValue<V>> ChooseWeightedRandomPartition(LinkedList<WeightedValue<V>> itemList, boolean favor_high, double error, int randomScale)
	{
		double minValue=0, maxValue=0;
		boolean first=true;
		double multiplier=(favor_high)?1:-1;
		
		for (WeightedValue<V> item:itemList)
		{
			if (first)
			{
				minValue=item.GetWeight();
				maxValue=item.GetWeight();
				first=false;
			}
			else
			{
				if (item.GetWeight()- maxValue>= -error/2)
					maxValue=item.GetWeight();
				if (minValue - item.GetWeight()>=-error/2)
					minValue=item.GetWeight();
			}
			
			
		}
		double selectionWidth=maxValue-minValue;
		
		if (Math.abs(selectionWidth)<=error)
			return itemList;
		
		
		double cutoff=Math.floor(randomScale*Math.random());
		
		double cutoffFraction=cutoff/randomScale;
		
		LinkedList<WeightedValue<V>> selectionList = new LinkedList<WeightedValue<V>>();
		
		double offsetFromMin=0;
		double selectionFraction;
		for (WeightedValue<V> item:itemList)
		{
			offsetFromMin=item.GetWeight()-minValue;
			selectionFraction=offsetFromMin/selectionWidth;
			if (multiplier*selectionFraction - multiplier*cutoffFraction>=error/2)
				selectionList.add(item);
		}
		
		return selectionList;
	}
	
	
	
	/**
	 * This is a test funciton used to prove that ChooseWeightedRandomFair is truy a
	 * uniform, unbiased sample from a set of weighted options
	 * 
	 * @param test
	 * @param totalInterations
	 */
	public static <V> void LongitudinalRandomTest(LinkedList<WeightedValue<V>> test, int totalInterations)
	{
		StringBuilder report = new StringBuilder();
		WeightedValue<V> chosenValue,stat;
		Hashtable<V,WeightedValue<V>> map = new Hashtable<V,WeightedValue<V>>();
		int totalCount=0;
		for (int i=0;i<totalInterations;i++)
		{
			chosenValue=ChooseWeightedRandomFair(test);
			if (map.containsKey(chosenValue.GetValue()))
			{
				stat=map.get(chosenValue.GetValue());
				stat.IncrementWeight();
			}
			else
			{
				stat=new WeightedValue<V>(chosenValue.GetValue(),1);
				map.put(chosenValue.GetValue(), stat);
			}
			
			totalCount++;
		}
		double mappedTotal=0;
		for (WeightedValue<V> result:test)
		{
			if (map.containsKey(result.GetValue()))
			{
				stat=map.get(result.GetValue());
				mappedTotal=stat.GetWeight();
			}
			else
				mappedTotal=0;
			report.append("The follow results apply:\n");
			report.append(String.format("Value %1s with weight %2s occurred a total of %3s times which is %4s percent\n", result.GetValue(),result.GetWeight(),mappedTotal,(int)(100.0*mappedTotal/totalCount)));
		}
		System.out.println(report);
		
	}

	
	public static int HashMapDiscreteVector(int index, int[][] allocationSet, boolean ifNotExistsCreateP)
	{
		int bufferSize=allocationSet.length;
		int baseIndex = index % bufferSize;
		int returnValue=bufferSize;
		int searchIndex;
		int allocatedIndex;
		// Check for exact match
		if (allocationSet[baseIndex][0] == index) 
			return baseIndex;
		// Check for unallocated match
		if (allocationSet[baseIndex][0] == -1)
		{
			if (ifNotExistsCreateP)
			{
				allocationSet[baseIndex][0]=index;
				returnValue =  baseIndex;
			}
			return returnValue;
		}
		
		searchIndex=baseIndex;
		// Move to end of linked list.  If this code is correct, this loop is guaranteed
		// to finish eventually
		while (allocationSet[searchIndex][1]!=-1) 
		{
			searchIndex=allocationSet[searchIndex][1];
			if (allocationSet[searchIndex][0]==index)
			{
				return 	searchIndex;
			}
		}
		// Trying to allocate a new location if possible
		if (ifNotExistsCreateP)
		{
			for (int i=1;i<=bufferSize;i++)
			{
				allocatedIndex=(searchIndex+i)%bufferSize;
				if (allocationSet[allocatedIndex][0]==-1) // index is free
				{
					allocationSet[allocatedIndex][0]=index;
					allocationSet[searchIndex][1]=allocatedIndex;
					returnValue=allocatedIndex;
					break;
				}
			}
		}
		
		return returnValue;
	}
	
	
	public static int HashMapDiscreteVector(int index, int[][] allocationSet, Object[] allocationList, boolean ifNotExistsCreateP)
	{
		int bufferSize=allocationSet.length;
		int baseIndex = index % bufferSize;
		int returnValue=bufferSize;
		int searchIndex;
		int allocatedIndex;
		Object priorObject;
		
		// Check for exact match
		if (allocationSet[baseIndex][0] == index) 
			return baseIndex;
		// Check for unallocated match
		if (allocationSet[baseIndex][0] == -1)
		{
			if (ifNotExistsCreateP)
			{
				allocationSet[baseIndex][0]=index;
				returnValue =  baseIndex;
			}
			return returnValue;
		}
		boolean squatter = (allocationSet[baseIndex][0] % bufferSize)!= baseIndex;
		searchIndex=baseIndex;
		// Move to end of linked list.  If this code is correct, this loop is guaranteed
		// to finish eventually
		while (allocationSet[searchIndex][1]!=-1) 
		{
			searchIndex=allocationSet[searchIndex][1];
			if (allocationSet[searchIndex][0]==index)
			{
				return 	searchIndex;
			}
		}
		// Trying to find a new location if possible
		if (ifNotExistsCreateP)
		{
			for (int i=1;i<=bufferSize;i++)
			{
				allocatedIndex=(searchIndex+i)%bufferSize;
				if (allocationSet[allocatedIndex][0]==-1) // index is free
				{
					if (squatter)
					{
						// swap memory locations
						priorObject=allocationList[baseIndex];
						allocationList[baseIndex]=allocationList[allocatedIndex];
						allocationList[allocatedIndex]=priorObject;
						// swap index locations
						allocationSet[allocatedIndex][0]=allocationSet[baseIndex][0];
						allocationSet[baseIndex][0]=index;
						
					}
					else
					{
						allocationSet[allocatedIndex][0]=index;
					}
					allocationSet[searchIndex][1]=allocatedIndex;
					return (squatter)?baseIndex:allocatedIndex;
					
				}
			}
		}
		
		return returnValue;
	}
	
	
	public static long HashMapDiscreteVector(long index, long[][] allocationSet, boolean ifNotExistsCreateP)
	{
		long bufferSize=allocationSet.length;
		long baseIndex = index % bufferSize;
		long returnValue=bufferSize;
		long searchIndex;
		long allocatedIndex;
		// Check for exact match
		if (allocationSet[(int)baseIndex][0] == index) 
			return baseIndex;
		// Check for unallocated match
		if (allocationSet[(int)baseIndex][0] == -1)
		{
			if (ifNotExistsCreateP)
			{
				allocationSet[(int)baseIndex][0]=index;
				returnValue =  baseIndex;
			}
			return returnValue;
		}
		
		searchIndex=baseIndex;
		// Move to end of linked list.  If this code is correct, this loop is guaranteed
		// to finish eventually
		while (allocationSet[(int)searchIndex][1]!=-1) 
		{
			searchIndex=allocationSet[(int)searchIndex][1];
			if (allocationSet[(int)searchIndex][0]==index)
			{
				return 	searchIndex;
			}
		}
		// Trying to allocate a new location if possible
		if (ifNotExistsCreateP)
		{
			for (int i=1;i<=bufferSize;i++)
			{
				allocatedIndex=(searchIndex+i)%bufferSize;
				if (allocationSet[(int)allocatedIndex][0]==-1) // index is free
				{
					allocationSet[(int)allocatedIndex][0]=index;
					allocationSet[(int)searchIndex][1]=allocatedIndex;
					returnValue=allocatedIndex;
					break;
				}
			}
		}
		
		return returnValue;
	}
	
	
	/**
	 * This method maps a discrete vector of N non-negative integral parameters to a
	 * single integer index.  For each parameter, you must specify in the argument
	 * {scales} the total  number of possible values for each parameter.  Each
	 * dimension of the vector should contain a number between 0 and 1 less than the
	 * scale for that dimension.
	 * 
	 * @param vector
	 * @param scales
	 */
	public static int MapDiscreteVectorToInt(int[] vector, int[] scales)
	{
		int index=vector[0];
		int product=1;
		for (int i=1;i<vector.length;i++)
		{	
			product*=scales[i-1];
			index+=product*vector[i];
			
		}
		return index;
	}
	
	public static int MapDiscreteVectorToInt(int[] vector, int[] scales, int sizeBound)
	{
		int product=1;
		int index=vector[0]%sizeBound;
		for (int i=1;i<vector.length;i++)
		{	
			
			product*=scales[i-1];
			if (((index+product*vector[i])%sizeBound)<index)
				product=1;
			index= (index+product*vector[i])%sizeBound;
			
		}
		return index;
	}
	
	public static int MapDiscreteVectorToInt(int[] vector, int scale, int sizeBound)
	{
		int product=1;
		int index=vector[0]%sizeBound;
		for (int i=1;i<vector.length;i++)
		{	
			
			product*=scale;
			if (((index+product*vector[i])%sizeBound)<index)
				product=1;
			index= (index+product*vector[i])%sizeBound;
			
		}
		return index;
	}
	
	
	public static <T> LinkedList<WeightedValue<T>> ListOveride(LinkedList<WeightedValue<T>> baseList, LinkedList<WeightedValue<T>> overrideList)
	{
		if (baseList==null)
			return baseList;
		LinkedList<WeightedValue<T>> output = new LinkedList<WeightedValue<T>>();
		WeightedValue<T> oValue;
		for (WeightedValue<T> bValue:baseList)
		{
			oValue = FindValueInList(overrideList, bValue);
			if (oValue!=null)
				output.add(oValue);
			else
				output.add(bValue);
		}
		
		return output;
	}
	
	
	/*
	 * This method returns a sublist of baseList that contain WeightedValues whose values can be found in 
	 * filterList
	 * 
	 */
	public static <T> LinkedList<WeightedValue<T>> GetListIntersection(LinkedList<WeightedValue<T>> filterList, LinkedList<WeightedValue<T>> baseList)
	{
		LinkedList<WeightedValue<T>> output = new LinkedList<WeightedValue<T>>();
		for (WeightedValue<T> val:baseList)
		{
			if (FindValueInList(filterList, val)!=null)
				output.add(val);
		}
		return output;
	}
	
	
	/*
	 * Returns true if inputList contains a weightedvalue whose value is the same as value 
	 * 
	 */
	public static <T> WeightedValue<T> FindValueInList(LinkedList<WeightedValue<T>> inputList,WeightedValue<T> value)
	{
		for (WeightedValue<T> compValue: inputList)
		{
			if (compValue.GetValue().equals(value.GetValue()))
				return compValue;
		}
		return null;
	}
	
	/**
	 * This method is an inverse map for MapDiscreteVectorToInt.  It maps an integer back to
	 * the original vector of integers that defined that value, given the scales
	 * @param index
	 * @param scales
	 */
	
	public static int[] ReverseMapIndexToVector(int index, int[] scales)
	{
		int I=index;
		int[] parameters = new int[scales.length];
		int N=scales.length-1;
		int prod=1;
		for (int i=0;i<=N;i++)
			prod*=scales[i];
		
		while (N>=0)
		{
			prod/=scales[N]; // prod = multiply(i,0,N-1,scales[i])
			
			parameters[N]=I/prod;
			I-=prod*parameters[N];
			N--;
		}
		return parameters;
	}
	
	public static <T> void IncrementAll(LinkedList<WeightedValue<T>> list1, double value)
	{
		for (WeightedValue<T> newValue:list1)
		{
			newValue.UpdateValue(value);
		}
	}
	
	public static <T> void IncrementAll(LinkedList<WeightedValue<T>> list1, double value, double minValue)
	{
		for (WeightedValue<T> newValue:list1)
		{
			newValue.SetWeight(Math.max(newValue.GetWeight(), value));
		}
	}
	
	public static int[][] DistribViewer(LinkedList<WeightedValue<Integer>> data)
	{
		if (data==null||data.size()==0)
			return null;
		
		int[][] out = new int[data.size()][2];
		int i=0;
		for (WeightedValue<Integer> d:data)
		{
			if (d!=null)
			{
				out[i][0] = d.GetValue().intValue();
				out[i][1] = (int)d.GetWeight();
			}
			else
				out[i]=null;
			
	      i++;
		}
		return out;
	}
	
	public static int[] DistribViewer(LinkedList<Integer> data)
	{
		if (data==null||data.size()==0)
			return null;
		
		int[] out = new int[data.size()];
		int i=0;
		for (Integer d:data)
		{
			if (d!=null)
				out[i] = d.intValue();
			else
				out[i]=0; // TODO: Figure out some better way of doing this
	      i++;
		}
		return out;
	}
	
	
	public static <T> LinkedList<WeightedValue<T>> MergeLists(LinkedList<WeightedValue<T>> list1, LinkedList<WeightedValue<T>> list2)
	{
		if ((list1==null)||(list2==null))
			return null;
		
		LinkedList<WeightedValue<T>> newList = new LinkedList<WeightedValue<T>>();
		HashMap<T,Double> keyValueMap = new HashMap<T, Double>();
		AddToMap(list1,keyValueMap);
		AddToMap(list2,keyValueMap);
		if (keyValueMap.size()==0)
			return null;
		else
		{
			WeightedValue<T> newValue;
			for (T key:keyValueMap.keySet())
			{
				newValue = new WeightedValue<T>(key,keyValueMap.get(key).doubleValue());
				newList.add(newValue);
			}
			return newList;
		}
	}
	
	public static <T> LinkedList<WeightedValue<T>> MergeSubtractLists(LinkedList<WeightedValue<T>> list1, LinkedList<WeightedValue<T>> list2)
	{
		if ((list1==null)||(list2==null))
			return null;
		LinkedList<WeightedValue<T>> newList = new LinkedList<WeightedValue<T>>();
		HashMap<T,Double> keyValueMap = new HashMap<T, Double>();
		AddToMap(list1,keyValueMap);
		AddToMap(list2,keyValueMap,false);
		if (keyValueMap.size()==0)
			return null;
		else
		{
			WeightedValue<T> newValue;
			for (T key:keyValueMap.keySet())
			{
				newValue = new WeightedValue<T>(key,keyValueMap.get(key).doubleValue());
				newList.add(newValue);
			}
			return newList;
		}
	}
	
	public static <T> LinkedList<WeightedValue<T>> MergeSubtractLists(LinkedList<WeightedValue<T>> list1, LinkedList<WeightedValue<T>> list2, double minValue)
	{
		if ((list1==null)||(list2==null))
			return null;
		LinkedList<WeightedValue<T>> newList = new LinkedList<WeightedValue<T>>();
		HashMap<T,Double> keyValueMap = new HashMap<T, Double>();
		AddToMap(list1,keyValueMap);
		AddToMap(list2,keyValueMap,false,minValue);
		if (keyValueMap.size()==0)
			return null;
		else
		{
			WeightedValue<T> newValue;
			for (T key:keyValueMap.keySet())
			{
				newValue = new WeightedValue<T>(key,keyValueMap.get(key).doubleValue());
				newList.add(newValue);
			}
			return newList;
		}
	}
	
	private static <T> void AddToMap(LinkedList<WeightedValue<T>> list1, HashMap<T,Double> map)
	{
		AddToMap(list1,map,true);
	}
	
	// Adds the elements of list1 to map.  If unionP is true then adds a key if it is not already there and
	// adds the sum of the weights of value of key to the exist key.  If unionP is false then only subtracts 
	// like values when map actually contains a value in list1
	// TODO: Need to change the meaning of this method.  
	private static <T> void AddToMap(LinkedList<WeightedValue<T>> list1, HashMap<T,Double> map, boolean unionP)
	{
		Double oldValue;
		double dValue;
		if (list1!=null)
		{
			for (WeightedValue<T> v1: list1)
			{
				if (map.containsKey(v1.GetValue()))
				{
					oldValue=map.get(v1.GetValue());
					if (unionP)
						dValue=oldValue.doubleValue() + v1.GetWeight();
					else
						dValue=oldValue.doubleValue() - v1.GetWeight();
					map.put(v1.GetValue(), new Double(dValue));
				}
				else
				{
					dValue=v1.GetWeight();
					if (unionP)
						map.put(v1.GetValue(), new Double(dValue));
				}
				
			}
		}
	}
	
	// Adds the elements of list1 to map.  If unionP is true then adds a key if it is not already there and
	// adds the sum of the weights of value of key to the exist key.  If unionP is false then only subtracts 
	// like values when map actually contains a value in list1
	// TODO: Need to change the meaning of this method.  
	private static <T> void AddToMap(LinkedList<WeightedValue<T>> list1, HashMap<T,Double> map, boolean unionP, double boundaryValue)
	{
		Double oldValue;
		double dValue;
		if (list1!=null)
		{
			for (WeightedValue<T> v1: list1)
			{
				if (map.containsKey(v1.GetValue()))
				{
					oldValue=map.get(v1.GetValue());
					if (unionP)
						dValue=Math.min(boundaryValue, oldValue.doubleValue() + v1.GetWeight());
					else
						dValue=Math.max(boundaryValue, oldValue.doubleValue() - v1.GetWeight());
					map.put(v1.GetValue(), new Double(dValue));
				}
				else
					dValue=v1.GetWeight();
				if (unionP)
					map.put(v1.GetValue(), new Double(dValue));
			}
		}
	}
	
	/*
	 * Sorts a Linked List of WeightedValues<T> Due to limitations with declaring generics with 
	 * java, this will look strange since generic types can't be used in array declarations.
	 * When bottomUpP is true then sorts in ascending order otherwise descending order
	 */
	public static <T> LinkedList<WeightedValue<T>> SortList(LinkedList<WeightedValue<T>> list,boolean ascendingP)
	{
		Object[] wList;
		wList = list.toArray();
		Arrays.sort(wList, GetWeightedValueComparator(ascendingP));
		LinkedList<WeightedValue<T>> newList = new LinkedList<WeightedValue<T>>();
		for (int i=0;i<wList.length;i++)
			newList.add((WeightedValue<T>)wList[i]);
		return newList;
	}
	
	/*
	 * Comparator of weighted values 
	 * 
	 */
	private static  Comparator GetWeightedValueComparator(boolean ascendingP)
	{
		if (ascendingP)
			return new Comparator()
			{
				public int compare(Object o1, Object o2)
				{
					WeightedValue v1 = (WeightedValue)o1;
					WeightedValue v2 = (WeightedValue)o2;
					if (v1.GetWeight()<v2.GetWeight())
						return -1;
					else if (v1.GetWeight()==v2.GetWeight())
						return 0;
					else
						return 1;
						
				}
				
				public boolean equals(Object obj)
				{
					return true;
				}
			};
		else
			return new Comparator()
			{
				public int compare(Object o1, Object o2)
				{
					WeightedValue v1 = (WeightedValue)o1;
					WeightedValue v2 = (WeightedValue)o2;
					if (v2.GetWeight()<v1.GetWeight())
						return -1;
					else if (v1.GetWeight()==v2.GetWeight())
						return 0;
					else
						return 1;
						
				}
				
				public boolean equals(Object obj)
				{
					return true;
				}
			};
	}
}
